home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 July / macformat-026.iso / mac / Shareware City / Developers / berkeleydb1.73 / Berkeley_db / hash / hash.h < prev    next >
Encoding:
C/C++ Source or Header  |  1993-07-31  |  9.7 KB  |  284 lines  |  [TEXT/????]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  *
  36.  *    @(#)hash.h    8.1 (Berkeley) 6/4/93
  37.  */
  38.  
  39. /* Operations */
  40. typedef enum {
  41.     HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
  42. } ACTION;
  43.  
  44. /* Buffer Management structures */
  45. typedef struct _bufhead BUFHEAD;
  46.  
  47. struct _bufhead {
  48.     BUFHEAD    *prev;        /* LRU links */
  49.     BUFHEAD    *next;        /* LRU links */
  50.     BUFHEAD    *ovfl;        /* Overflow page buffer header */
  51.     u_int     addr;        /* Address of this page */
  52.     char    *page;        /* Actual page data */
  53.     char     flags;
  54. #define    BUF_MOD        0x0001
  55. #define BUF_DISK    0x0002
  56. #define    BUF_BUCKET    0x0004
  57. #define    BUF_PIN        0x0008
  58. };
  59.  
  60. #define IS_BUCKET(X)    ((X) & BUF_BUCKET)
  61.  
  62. typedef BUFHEAD **SEGMENT;
  63.  
  64. /* Hash Table Information */
  65. typedef struct hashhdr {    /* Disk resident portion */
  66.     int    magic;        /* Magic NO for hash tables */
  67.     int    version;    /* Version ID */
  68.     long    lorder;        /* Byte Order */
  69.     int    bsize;        /* Bucket/Page Size */
  70.     int    bshift;        /* Bucket shift */
  71.     int    dsize;        /* Directory Size */
  72.     int    ssize;        /* Segment Size */
  73.     int    sshift;        /* Segment shift */
  74.     int    ovfl_point;    /* Where overflow pages are being allocated */
  75.     int    last_freed;    /* Last overflow page freed */
  76.     int    max_bucket;    /* ID of Maximum bucket in use */
  77.     int    high_mask;    /* Mask to modulo into entire table */
  78.     int    low_mask;    /* Mask to modulo into lower half of table */
  79.     int    ffactor;    /* Fill factor */
  80.     int    nkeys;        /* Number of keys in hash table */
  81.     int    hdrpages;    /* Size of table header */
  82.     int    h_charkey;    /* value of hash(CHARKEY) */
  83. #define NCACHED    32        /* number of bit maps and spare points */
  84.     int    spares[NCACHED];/* spare pages for overflow */
  85.     u_short    bitmaps[NCACHED];    /* address of overflow page bitmaps */
  86. } HASHHDR;
  87.  
  88. typedef struct htab {        /* Memory resident data structure */
  89.     HASHHDR hdr;        /* Header */
  90.     int    nsegs;        /* Number of allocated segments */
  91.     int    exsegs;        /* Number of extra allocated segments */
  92.     int    (*hash) ();    /* Hash Function */
  93.     int    flags;        /* Flag values */
  94.     int    fp;        /* File pointer */
  95.     char    *tmp_buf;    /* Temporary Buffer for BIG data */
  96.     char    *tmp_key;    /* Temporary Buffer for BIG keys */
  97.     BUFHEAD *cpage;        /* Current page */
  98.     int    cbucket;    /* Current bucket */
  99.     int    cndx;        /* Index of next item on cpage */
  100.     int    errno;        /* Error Number -- for DBM compatability */
  101.     int    new_file;    /* Indicates if fd is backing store or no */
  102.     int    save_file;    /* Indicates whether we need to flush file at
  103.                  * exit */
  104.     u_long *mapp[NCACHED];    /* Pointers to page maps */
  105.     int    nmaps;        /* Initial number of bitmaps */
  106.     int    nbufs;        /* Number of buffers left to allocate */
  107.     BUFHEAD bufhead;    /* Header of buffer lru list */
  108.     SEGMENT *dir;        /* Hash Bucket directory */
  109. } HTAB;
  110.  
  111. /*
  112.  * Constants
  113.  */
  114. #define    MAX_BSIZE        65536        /* 2^16 */
  115. #define MIN_BUFFERS        6
  116. #define MINHDRSIZE        512
  117. #define DEF_BUFSIZE        65536        /* 64 K */
  118. #define DEF_BUCKET_SIZE        4096
  119. #define DEF_BUCKET_SHIFT    12        /* log2(BUCKET) */
  120. #define DEF_SEGSIZE        256
  121. #define DEF_SEGSIZE_SHIFT    8        /* log2(SEGSIZE)     */
  122. #define DEF_DIRSIZE        256
  123. #define DEF_FFACTOR        65536
  124. #define MIN_FFACTOR        4
  125. #define SPLTMAX            8
  126. #define CHARKEY            "%$sniglet^&"
  127. #define NUMKEY            1038583
  128. #define BYTE_SHIFT        3
  129. #define INT_TO_BYTE        2
  130. #define INT_BYTE_SHIFT        5
  131. #define ALL_SET            ((u_int)0xFFFFFFFF)
  132. #define ALL_CLEAR        0
  133.  
  134. #define PTROF(X)    ((BUFHEAD *)((u_int)(X)&~0x3))
  135. #define ISMOD(X)    ((u_int)(X)&0x1)
  136. #define DOMOD(X)    ((X) = (char *)((u_int)(X)|0x1))
  137. #define ISDISK(X)    ((u_int)(X)&0x2)
  138. #define DODISK(X)    ((X) = (char *)((u_int)(X)|0x2))
  139.  
  140. #define BITS_PER_MAP    32
  141.  
  142. /* Given the address of the beginning of a big map, clear/set the nth bit */
  143. #define CLRBIT(A, N)    ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
  144. #define SETBIT(A, N)    ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
  145. #define ISSET(A, N)    ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
  146.  
  147. /* Overflow management */
  148. /*
  149.  * Overflow page numbers are allocated per split point.  At each doubling of
  150.  * the table, we can allocate extra pages.  So, an overflow page number has
  151.  * the top 5 bits indicate which split point and the lower 11 bits indicate
  152.  * which page at that split point is indicated (pages within split points are
  153.  * numberered starting with 1).
  154.  */
  155.  
  156. #define SPLITSHIFT    11
  157. #define SPLITMASK    0x7FF
  158. #define SPLITNUM(N)    (((u_int)(N)) >> SPLITSHIFT)
  159. #define OPAGENUM(N)    ((N) & SPLITMASK)
  160. #define    OADDR_OF(S,O)    ((u_int)((u_int)(S) << SPLITSHIFT) + (O))
  161.  
  162. #define BUCKET_TO_PAGE(B) \
  163.     (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0)
  164. #define OADDR_TO_PAGE(B)     \
  165.     BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B));
  166.  
  167. /*
  168.  * page.h contains a detailed description of the page format.
  169.  *
  170.  * Normally, keys and data are accessed from offset tables in the top of
  171.  * each page which point to the beginning of the key and data.  There are
  172.  * four flag values which may be stored in these offset tables which indicate
  173.  * the following:
  174.  *
  175.  *
  176.  * OVFLPAGE    Rather than a key data pair, this pair contains
  177.  *        the address of an overflow page.  The format of
  178.  *        the pair is:
  179.  *            OVERFLOW_PAGE_NUMBER OVFLPAGE
  180.  *
  181.  * PARTIAL_KEY    This must be the first key/data pair on a page
  182.  *        and implies that page contains only a partial key.
  183.  *        That is, the key is too big to fit on a single page
  184.  *        so it starts on this page and continues on the next.
  185.  *        The format of the page is:
  186.  *            KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
  187.  *        
  188.  *            KEY_OFF -- offset of the beginning of the key
  189.  *            PARTIAL_KEY -- 1
  190.  *            OVFL_PAGENO - page number of the next overflow page
  191.  *            OVFLPAGE -- 0
  192.  *
  193.  * FULL_KEY    This must be the first key/data pair on the page.  It
  194.  *        is used in two cases.
  195.  *
  196.  *        Case 1:
  197.  *            There is a complete key on the page but no data
  198.  *            (because it wouldn't fit).  The next page contains
  199.  *            the data.
  200.  *
  201.  *            Page format it:
  202.  *            KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
  203.  *
  204.  *            KEY_OFF -- offset of the beginning of the key
  205.  *            FULL_KEY -- 2
  206.  *            OVFL_PAGENO - page number of the next overflow page
  207.  *            OVFLPAGE -- 0
  208.  *
  209.  *        Case 2:
  210.  *            This page contains no key, but part of a large
  211.  *            data field, which is continued on the next page.
  212.  *
  213.  *            Page format it:
  214.  *            DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
  215.  *
  216.  *            KEY_OFF -- offset of the beginning of the data on
  217.  *                this page
  218.  *            FULL_KEY -- 2
  219.  *            OVFL_PAGENO - page number of the next overflow page
  220.  *            OVFLPAGE -- 0
  221.  *
  222.  * FULL_KEY_DATA 
  223.  *        This must be the first key/data pair on the page.
  224.  *        There are two cases:
  225.  *
  226.  *        Case 1:
  227.  *            This page contains a key and the beginning of the
  228.  *            data field, but the data field is continued on the
  229.  *            next page.
  230.  *
  231.  *            Page format is:
  232.  *            KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
  233.  *
  234.  *            KEY_OFF -- offset of the beginning of the key
  235.  *            FULL_KEY_DATA -- 3
  236.  *            OVFL_PAGENO - page number of the next overflow page
  237.  *            DATA_OFF -- offset of the beginning of the data
  238.  *
  239.  *        Case 2:
  240.  *            This page contains the last page of a big data pair.
  241.  *            There is no key, only the  tail end of the data
  242.  *            on this page.
  243.  *
  244.  *            Page format is:
  245.  *            DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
  246.  *
  247.  *            DATA_OFF -- offset of the beginning of the data on
  248.  *                this page
  249.  *            FULL_KEY_DATA -- 3
  250.  *            OVFL_PAGENO - page number of the next overflow page
  251.  *            OVFLPAGE -- 0
  252.  *
  253.  *            OVFL_PAGENO and OVFLPAGE are optional (they are
  254.  *            not present if there is no next page).
  255.  */
  256.  
  257. #define OVFLPAGE    0
  258. #define PARTIAL_KEY    1
  259. #define FULL_KEY    2
  260. #define FULL_KEY_DATA    3
  261. #define    REAL_KEY    4
  262.  
  263. /* Short hands for accessing structure */
  264. #define BSIZE        hdr.bsize
  265. #define BSHIFT        hdr.bshift
  266. #define DSIZE        hdr.dsize
  267. #define SGSIZE        hdr.ssize
  268. #define SSHIFT        hdr.sshift
  269. #define LORDER        hdr.lorder
  270. #define OVFL_POINT    hdr.ovfl_point
  271. #define    LAST_FREED    hdr.last_freed
  272. #define MAX_BUCKET    hdr.max_bucket
  273. #define FFACTOR        hdr.ffactor
  274. #define HIGH_MASK    hdr.high_mask
  275. #define LOW_MASK    hdr.low_mask
  276. #define NKEYS        hdr.nkeys
  277. #define HDRPAGES    hdr.hdrpages
  278. #define SPARES        hdr.spares
  279. #define BITMAPS        hdr.bitmaps
  280. #define VERSION        hdr.version
  281. #define MAGIC        hdr.magic
  282. #define NEXT_FREE    hdr.next_free
  283. #define H_CHARKEY    hdr.h_charkey
  284.